/* Prasann Gamit
E845H824
homework 8
cs 460*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
double IStime, BStime;
int heapsize;
void max_heapify(int *I,int i);
char UserMenu( char *c )
{
	char choice;
	for ( choice = '0'; choice - 48 <= 0 || choice - 48 > 7; )
	{
		printf ( "\n----------------Menu----------------\n" );
		printf ( "0)Exit\n" );
		printf ( "1)Populate array\n" );
		printf ( "2)Copy array\n" );
		printf ( "3)Display array (first 10 items)\n" );
		printf ( "4)Shell Sort Ascending\n" );
		printf ( "5)Heap Sort Ascending\n" );
		printf ( "6)Calculate Time for Shell Sort\n" );
		printf ( "7)Calculate Time for Heap Sort\n" );
		printf ( "Please select an option:\n" );
		scanf ( "\n%c", &choice );
		if ( choice - 48 <= 0 && choice - 48 > 7 )
		{
			printf ( "Option Error: No such option!\n" );
		}
		else if ( choice == '0' )
		return '0';
	}
	return choice;
}
//function to populate array
void PopulateArrayDes ( int *A )
{
	int i,j;
	srand ( time (0) );
	j=0;
	for ( i = 100000; i >0; i-- )
	{
		A[j]=i;j++;
	}
	printf ( "\nPopulating done." );
}
//function to copu array
void CopyArrays ( int *A1, int *A2 )
{
	int i;
	for ( i = 0; i < 100000; i++)
	{
		A2[i] = A1[i];
	}
	printf ( "\ncopying done\n" );
}
//printing tha array for 10 items
void DisplayArray10Items ( int *A )
{
	int i;
	for ( i = 0; i < 10; i++ )
	printf ( "%d\n ", A[i] );
}
//Shel sort 
void ShellsortAsc ( int *B )
{
	int i, j, increment, temp,number_of_elements;
	number_of_elements=100000;
	for(increment = number_of_elements/2;increment > 0; increment /= 2)
	{
		for(i = increment; i<number_of_elements; i++)
		{
			temp = B[i];
			for(j = i; j >= increment ;j-=increment)
			{
				if(temp < B[j-increment])
				{
					B[j] = B[j-increment];
				}
				else
				{
					break;
				}
			}
			B[j] = temp;
		}
	}
	printf("\nShel sort done");
}

void swap(int *a ,int *b)
{
	int temp = *a;
	*a= *b;
	*b= temp;
}

void build_max_heap(int *I,int len)
{
	heapsize = len;
	int i;
	for(i =len/2;i>=0;i--)
	{
		max_heapify(I,i);
	}
}

void max_heapify(int *I,int i)
{
	int l=2*i,r=2*i+1,largest;
	if(l<heapsize && I[l]>I[i])
	largest = l;
	else
	largest = i;
	if(r<heapsize && I[r]>I[largest])
	largest = r;
	if(largest != i)
	{
		swap(&I[i],&I[largest]);
		max_heapify(I,largest);
	}
}

//Heap sort
void HeapsortAsc (int *I )
{
	int i,len;len = 100000;
	build_max_heap(I,len);
	for(i= len-1;i>=1;i--)
	{
		swap(&I[0],&I[i]);
		heapsize = heapsize -1;
		max_heapify(I,0);
	}
	printf("\nHeap sort done");
}
//calculate time for shell sort
int CalculateTimeSS ( int *A )
{
	time_t Begin, End;
	Begin = clock ();
	ShellsortAsc ( A );
	End = clock ();
	BStime = ( double ) ( End - Begin ) / CLOCKS_PER_SEC;
	return BStime;
}
//calculate time for insertion sort
int CalculateTimeHS ( int *A )
{
	time_t Begin, End;
	Begin = clock ();
	HeapsortAsc ( A );
	End = clock ();
	IStime = ( double ) ( End - Begin ) / CLOCKS_PER_SEC;
	return IStime;
}
//function to exit program
void exitProg ()
{
	exit (1);
}
//starting main
int main(void)
{
	char cSystem = '0';
	int Array1[100000], Array2[100000];
	printf ( "Welcome to CS460 HW 08 solution!" );
	for ( cSystem = UserMenu ( &cSystem ); cSystem - 48; cSystem = UserMenu ( &cSystem ) )
	{
		switch ( cSystem - 48 )
		{
			case 1:
				PopulateArrayDes ( Array1 );//populate array
			break;
			case 2:
				CopyArrays ( Array1, Array2 );//copy array
			break;
			case 3:
				printf ( "Array 1:\n" );
				DisplayArray10Items ( Array1 );//display array 
				printf ( "\nArray 2:\n" );
				DisplayArray10Items ( Array2 );//display array
				printf ( "\n" );
			break;
			case 4:
				CalculateTimeSS ( Array1 );//calculate bubble sort time
			break;
			case 5:
				CalculateTimeHS ( Array1 );//calculate insertion sort time
			break;
			case 6:
				printf ( "Shel sort time is %lf\n", BStime );//print BStime
			break;
			case 7:
				printf ( "Heap sort time is %lf\n", IStime );//print IStime
			break;
		}
	}
	exitProg ();
	return 0;
}
